package com.hc.programming.tree;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
 * 假设二叉树中至少有一个节点。
 * <p>
 * 示例 1:
 * <a href="./找树左下角的值-示例1.png">示例1</a>
 * 输入: root = [2,1,3]
 * 输出: 1
 * 示例 2:
 * <a href="./找树左下角的值-示例2.png">示例2</a>
 * 输入: [1,2,3,4,null,5,6,null,null,7]
 * 输出: 7
 * <p>
 * 提示:
 * 二叉树的节点个数的范围是 [1,10^4]
 * -2^31 <= Node.val <= 2^31 - 1
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/10/15 9:29
 */
public class 找树左下角的值 {
    public static void main(String[] args) {
        Integer[] arr = new Integer[]{2, 1, 3};
        TreeNode tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=1,--" + findBottomLeftValue(tree));
        arr = new Integer[]{1, 2, 3, 4, null, 5, 6, null, null, 7};
        tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=7,--" + findBottomLeftValue(tree));
    }

    public static int findBottomLeftValue(TreeNode root) {
//        return 迭代(root);

        VAL = 0;
        LEVEL = 0;
        递归(root, 1);
        return VAL;
    }

    static int VAL = 0;
    static int LEVEL = 0;

    private static void 递归(TreeNode root, int level) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            if (level > LEVEL) {
                LEVEL = level;
                VAL = root.val;
            }
        }
        if (root.left != null) 递归(root.left, level + 1);
        if (root.right != null) 递归(root.right, level + 1);
    }

    private static int 迭代(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int val = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
                if (i == 0) val = node.val;
            }
        }
        return val;
    }
}
